﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LeetCode
{
    public class TwoSum : IRun
    {
        public void Run()
        {
            int[] DemoValue = { 1, 3, 2, 2, 7, 11, 15 };

            foreach (var item in DemoValue)
            {
                Console.Write(item + "  ");
            }
            Console.WriteLine();

            int _Target = 13;
            Console.WriteLine(_Target);

            foreach (var item in Method4(DemoValue, _Target))
            {
                Console.Write(item + "  ");
            }
        }

        /// <summary>
        /// 暴力循环 
        /// </summary>
        private int[] Method1(int[] nums, int target)
        {
            for (int i = 0; i < nums.Length; i++)
            {
                for (int j = i + 1; j < nums.Length; j++)
                {
                    if (target == (nums[i] + nums[j]))
                    {
                        return new int[] { nums[i], nums[j] };
                    }
                }
            }
            return null;
        }

        /// <summary>
        /// 通过字典
        /// 判断差值是否存在于字典中,若存在,通过遍历,查找到Index
        /// 故对数组也可进行类似操作,但注意First(若数据不存在,抛出异常)与FirstDefault(若数据不存在,返回数组第一个元素)方法,
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        private int[] Method2(int[] nums, int target)
        {
            // key与value,均为Object
            //Hashtable _HashTable = new Hashtable();
            // key与value,为泛型,可自定义类型

            Dictionary<int, int> _Dictionary = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++)
            {
                _Dictionary.Add(i, nums[i]);
            }
            int _DifferenceValue;
            foreach (var item in _Dictionary)
            {
                _DifferenceValue = target - item.Value;
                if (_Dictionary.ContainsValue(_DifferenceValue))
                {
                    foreach (var item1 in _Dictionary)
                    {
                        if (item1.Value == _DifferenceValue)
                        {
                            return new int[] { item.Value, item1.Value };
                        }
                    }
                }
            }

            return null;
        }

        /// <summary>
        /// 通过字典
        /// 有限制:自组中,数据不能重复
        /// 将字典value存储索引,key存取值
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        private int[] Method4(int[] nums, int target)
        {
            // key与value,为泛型,可自定义类型
            Dictionary<int, int> _Dictionary = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if (!_Dictionary.ContainsKey(nums[i]))
                {
                    _Dictionary.Add(nums[i], i);
                }
            }

            int _DifferenceValue;
            foreach (var item in _Dictionary)
            {
                _DifferenceValue = target - item.Key;
                if (_Dictionary.ContainsKey(_DifferenceValue) && _Dictionary[_DifferenceValue] != item.Value)
                {
                    return new int[] { item.Value, _Dictionary[_DifferenceValue] };
                }
            }

            return new int[] { 0, 0 };
        }

        /// <summary>
        /// 
        /// </summary>
        private int[] Method5(int[] nums, int target)
        {
            Dictionary<int, int> contain = new Dictionary<int, int>();
            for (int i = 0; i < nums.Length; i++)
            {
                if (contain.ContainsKey(target - nums[i]))
                    return new int[] { contain[target - nums[i]], i };
                else if (!contain.ContainsKey(nums[i]))
                    contain.Add(nums[i], i);
            }
            return new int[] { 0, 0 };

        }
    }
}
